package leetcode.editor.template.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

// 递归进行层序遍历
public class TraversalToLevelTraverse {
    class TreeNode {
        int val;
        TreeNode left, right;

        public TreeNode() {
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    List<List<Integer>> res = new ArrayList<>();

    List<List<Integer>> levelTraverse(TreeNode root) {
        if (root == null) return null;
        // 从第0层开始
        traversal(root, 0);
        return res;
    }

    void traversal(TreeNode root, int depth) {
        if (root == null) return;

        // 前序位置，看看是否已经存储 depth 层的节点了
        if (res.size() <= depth) {
            // 第一次进入 depth 层
            res.add(new ArrayList<>());
        }

        // 前序位置，在 depth 层添加 root 节点的值
        traversal(root.left, depth + 1);
        traversal(root.right, depth + 1);
    }
}
